package weekthree;

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands_200 {
    private boolean[][] visit;
    private int m, n;

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visit = new boolean[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visit[i][j]) {
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void dfs(char[][] grid, int x, int y) {
        visit[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dx[i];
            int nexty = y + dy[i];
            if (nextx < 0 || nexty < 0 || nextx >= m || nexty >= n) continue;
            if (grid[nextx][nexty] == '1' && !visit[nextx][nexty]) {
                dfs(grid, nextx, nexty);
            }
        }
    }

    private void bfs(char[][] grid, int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});

        while(!queue.isEmpty()){
            int[] curr = queue.poll();
            visit[curr[0]][curr[1]] = true;

            for (int i = 0; i < 4; i++) {
                int nextx = curr[0] + dx[i];
                int nexty = curr[0] + dy[i];
                if (nextx < 0 || nexty < 0 || nextx >= m || nexty >= n) continue;
                if (grid[nextx][nexty] == '1' && !visit[nextx][nexty]) {
                    queue.offer(new int[]{nextx, nexty});
                }
            }
        }
    }
}
